首页 > 试题广场 >

走方格的方案数

[编程题]走方格的方案数

热度指数：122096 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

请计算n*m的棋盘格子（n为横向的格子数，m为竖向的格子数）从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。

注：沿棋盘格之间的边缘线行走

数据范围： $1 \le n,m \le 8 \$

输入描述:

输入两个正整数n和m，用空格隔开。(1≤n,m≤8)

输出描述:

输出一行结果

示例1

输入

2 2

输出

算法知识视频讲解

Python 3

Scorpion201901072009417

import sys

def countPath(n, m):

"""

dp函数：到达（n，m）的路径数量

base case (0, 0)为1，因为已经在目标位置，没有其他路径

"""

if n < 0 or m < 0:

return 0

if n == 0 or m == 0: # 到达棋盘的边缘，只有沿边一种走法

return 1

# 若非边缘情况，从上一个或左一个位置到达当前位置。

# ！！！注意：因为到达(n-1,m)或(n,m-1)时，此时只有一种选择到达（n,m)所以不需要再加1

return countPath(n - 1, m) + countPath(n, m - 1)

# 获取输入

line = input().split(' ')

n, m = int(line[0]), int(line[1])

print(countPath(n,m))

编辑于 2024-04-05 18:23:38 回复(0)

Python 3

牛客560069418号

如果目标点与起点不在一条水平或垂直直线上，创造两个新的目标点，分别横纵坐标-1，直到递归到在直线的情况，直线时只有一条路径。

a = list(map(int,input().split()))
def loop(location):
    if not location[0]&nbs***bsp;not location[1]:
        return 1
    else:
        return loop([location[0] -1,location[1]]) + loop([location[0],location[1]-1])
print(loop(a))

发表于 2022-08-27 14:48:12 回复(0)

Python 3

进击的皮皮举

递归法：

从m,n开始，向右走一步，m*n的方案数==(m-1)*n的方案数

向下走一步，m*n的方案数==m*(n-1)的方案数

由此得到递归式子：f(m,n)=f(m-1,n)+f(m,n-1)

在n=1时，方案数为m+1

在m=1时，方案数为n+1

n,m=map(int,input().split())

def f(n,m):
    
    if n==1 :
        return m+1
    elif m==1:
        return n+1
    else:
        
        return f(n-1,m)+f(n,m-1)
print(f(n,m))

发表于 2022-08-15 16:33:43 回复(0)

Python 3

Justinshadow

def fun(n:int,m:int):
    if n == 0&nbs***bsp;m == 0:
        return 1
    else:
        return fun(n-1,m)+fun(n,m-1)

n,m = map(int,input().split())
print(fun(n,m))

发表于 2022-08-09 17:58:39 回复(0)

Python 3

来个offer叭！

get_str = input().split(' ')
n, m = int(get_str[0]), int(get_str[1])
# (n+1)*(m+1)的二维dp数组
dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(n+1):
    for j in range(m+1):
        # dp数组初始化
        # 原点时0种走法
        if i==0 and j==0:
            dp[i][j] = 0
        # 从原点向下走一步共1种走法
        # elif i==0 and j==1:
        # 这里可以考虑优化？当退到左边界或上边界时仅剩一种走法
        elif i==0:
            dp[i][j] = 1
        # 从原点向右走一步共1种走法
        # elif i==1 and j==0:
        elif j==0:
            dp[i][j] = 1
        # [i][j]点的走法=左边一个点走法+上面一个点的走法
        # 即：dp[i][j] = dp[i-1][j] + dp[i][j-1]
        else:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(dp[n][m])

发表于 2022-07-30 17:46:31 回复(0)

Python 3

dk斗志昂扬

#捋清了递归思想，这道题真是再简单不过了
def dp(a, b):
    if a > 0 and b > 0:
        return dp(a-1, b)+dp(a, b-1)
    else:
        return 1

n, m = map(int, input().split())
print(dp(n, m))

发表于 2022-07-19 01:09:03 回复(0)

Python 3

风软一江山

看起来像是一个递归问题

def fun(n,m):
    if n == 1 and m == 1:
        return 2
    elif n == 1 and m != 1:
        return m+1
    elif n != 1 and m == 1:
        return n+1
    else:
        return fun(n-1,m) + fun(n,m-1)
a,b = map(int,input().split())
print(fun(a,b))

发表于 2022-06-30 17:12:52 回复(0)

Python 3

test8794

动态规划：

dp[i][j]代表i*j方格的方案数，归纳一下转移方程就可以了，比较简单。

'''
Tag: 动态规划
'''

def walk_solutions(n, m):
    n += 1
    m += 1
    dp = [[0 for _ in range(n)] for _ in range(m)]
    
    for i in range(1, m):
        for j in range(1, n):
            if i == 1:
                dp[i][j] = j + 1
            elif j == 1:
                dp[i][j] = i + 1
            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[i][j]

n, m = map(int, input().split())
print(walk_solutions(n, m))

发表于 2022-06-23 02:05:26 回复(0)

Python 3

鱼説

while 1:
    try:
        m,n = map(int,input().split())
        dp=[[0 for i in range(n+1)] for j in range(m+1)]
        for j in range(1,n+1):
            dp[0][j]=1
        for i in range(1,m+1):
            dp[i][0]=1
        for i in range(1,m+1):
            for j in range(1,n+1):
                dp[i][j]=dp[i-1][j]+dp[i][j-1]
        print(dp[m][n])
    except:
        break

发表于 2022-06-11 15:49:30 回复(0)

Python 3

小枫叶666

#参考：https://leetcode.cn/problems/unique-paths/solution/dai-ma-sui-xiang-lu-dong-gui-wu-bu-qu-xi-1vkb/
#DFS
m,n = map(int,input().split(" "))
directions=[(1,0),(0,1)]
def dfs(x,y):
#     pass
    if x > m&nbs***bsp;y > n:
        return 0
    
    if x == m and y == n:
        return 1
    return dfs(x+1,y)+dfs(x, y+1)
res = dfs(0,0)
print(res)


#DP
n,m = map(int,input().split(" "))
n=n+1
m=m+1
dp=[[0]*m for _ in range(n)] 
for j in range(m):
    dp[0][j] = 1
for i in range(n):
    dp[i][0] = 1
for i in range(1,n):
    for j in range(1,m):
        dp[i][j]= dp[i-1][j]+ dp[i][j-1]
print(dp[-1][-1])

发表于 2022-06-06 17:00:05 回复(0)

Python 3

xxooxx

s = input().split(" ")
l = list(map(int,s))
a=l[0]
b=l[1]
ll = []

for i in range(0, l[0]+1):
    ll.append([1])
    for j in range(0, l[1]):
        ll[i].append(0)


for i in range(0, b+1):
    ll[0][i]=1



for i in range(1,a +1):  #hang
    for j in range(1, b+ 1):    #lie

            ll[i][j]=ll[i][j-1]+ll[i-1][j]

print(ll[a][b])

发表于 2022-06-02 13:59:28 回复(0)

Python 3

牛客31170954号

x, y = map(int, input().split())
A = ["0", "1"] #0往下，1往右
S = ["0", "1"]
while True:
A = S
k = 0
for i in S:
if len(i) < x + y:
k += 1
if k == 0:
break
for i in A:
if len(i) < x + y:
n = i.count("0")
m = i.count("1")
if i.count("0") < y:
S.append(i + '0')
if i.count("1") < x:
S.append(i + '1')
if len(i) < x + y:
S.remove(i)

print(len(S))

发表于 2022-05-30 16:16:01 回复(0)

Python 3

牛客475421635号

def fun():
a = [int(i) for i in input().split(" ")]
b = [[0]*(a[0]+1) for i in range(a[1]+1)]
for m in range(a[1]+1):
for n in range(a[0]+1):
if m != 0 and n == 0:
b[m][n] = 1
elif n != 0 and m == 0:
b[m][n] = 1
else:
b[m][n] = b[m-1][n] + b[m][n-1]
print(b[-1][-1])

if __name__ == "__main__":
fun()

发表于 2022-05-22 00:40:47 回复(0)

Python 3

worldpuppy

m,n=input().split(' ')
d=1
s=1
for i in range(int(m)+1,int(m)+int(n)+1):
    d=d*i 
for i in range(1,int(n)+1):
    s=s*i 
print(round(d/s))

发表于 2022-05-18 19:18:54 回复(0)

Python 3

HeartBeating

#容易想到的是，在第一步时，可以选择向右或者向下，
#只需要当前的路径选择上加上(n,m−1)(n,m-1)(n,m−1)和(n−1,m)(n-1,m)(n−1,m)的矩阵路径选择即可。而(n,m−1)(n,m-1)(n,m−1)与(n−1,m)(n-1,m)(n−1,m)又是(n,m)(n,m)(n,m)的子问题，
#可以继续递归下去。
#只需要用iii，jjj表示当前位置，后续限制边界的向下或者向右即可。

def func(x,y):
    if x < 0&nbs***bsp;y < 0:
        return 0
    elif x == 0&nbs***bsp;y == 0:
        return 1
    else:
        return func(x-1, y)+func(x, y-1)

while True:
    try:
        a,b = map(int,input().split())
        c = func(a, b)
        print(c)
    except:
        break

发表于 2022-05-02 00:35:33 回复(0)

Python 3

牛客991913212号

# 输入行数和列数
n,m=map(int,input().split(" "))
# 边界条件
# 当只有一行的时候
if m ==1:
    print(n+1)
# 当只有一列的时候
elif n ==1:
    print(m+1)
else:
    # 构建dp数组
    dp=[[1]*(n+1) for _ in range(m+1)]
    # print(dp)
    dp[0][1]=1
    dp[1][0]=1
    for i in range(1,m+1):
        for j in range(1,n+1):
            # 状态方程
            # 表示达到第i行第j列的方法
            dp[i][j]=dp[i-1][j] +dp[i][j-1]
    print(dp[m][n])

发表于 2022-04-28 12:58:22 回复(0)